/*
@Copyright:LintCode
@Author:   tjyemail
@Problem:  http://www.lintcode.com/problem/backpack-ii
@Language: C++
@Datetime: 16-02-09 05:42
*/

class Solution {
public:
    /**
     * @param m: An integer m denotes the size of a backpack
     * @param A & V: Given n items with size A[i] and value V[i]
     * @return: The maximum value
     */
    int backPackII(int m, vector<int> A, vector<int> V) {
        // write your code here
        vector<int> DP(m+1);
        for(int i=0;i<A.size();++i)
            for(int j=m;j>=0;--j)
                if (j>=A[i] && DP[j]<DP[j-A[i]]+V[i])
                    DP[j] = DP[j-A[i]]+V[i];
        return DP[m];
    }
};